package com.wjy.Data_Structure.tree;

import com.wjy.Data_Structure.linearlist.common.Node;

//二叉树存储结构结点定义
public class BinTreeNode implements Node {
	private Object data;//数据域
	private BinTreeNode parent;//父结点
	private BinTreeNode lChild;//左孩子
	private BinTreeNode rChild;//右孩子
	private int height; //以该结点为根的子树的高度
	private int size;//该结点孙数(包括结点本身)

	public BinTreeNode() {
		this(null);
	}

	public BinTreeNode(Object e) {
		data = e;
		height = 0;
		size = 1;
		parent = lChild = rChild = null;
	}

	/*****************Node接口方法***************/
	@Override
	public Object getData() {
		return data;
	}

	@Override
	public void setData(Object obj) {
		this.data = obj;
	}

	/******辅助方法,判断当前结点位置情况******/
	/**
	 * 判断是否有父亲
	 * @return
	 */
	public boolean hasParent() {
		return this.parent != null;
	}

	/**
	 * 判断是否有左孩子
	 * @return
	 */
	public boolean hasLChild() {
		return this.lChild != null;
	}

	/**
	 * 判断是否有右孩子
	 * @return
	 */
	public boolean hasRChild() {
		return this.rChild != null;
	}

	/**
	 * 判断是否为叶子结点
	 * @return
	 */
	public boolean isLeaf() {
		return !hasLChild() && !hasRChild();
	}

	/**
	 * 判断是否为某结点的左孩子
	 * @return
	 */
	public boolean isLChild() {
		return hasParent() && this == parent.lChild;
	}

	/**
	 * 判断是否为某结点的右孩子
	 * @return
	 */
	public boolean isRChild() {
		return hasParent() && this == parent.rChild;
	}

	/**********与height相关的方法*******/
	/**
	 *取结点的高度,即以该结点为根的子树的高度
	 * @return
	 */
	public int getHeight() {
		return height;
	}

	/**
	 * 更新当前结点及其祖先的高度
	 */
	public void updateHeight() {
		int newH = 0;//新高度初始化为0，高度等于左右子树高度加1中的大者
		if (this.hasLChild())
			newH = Math.max(newH, 1 + this.getLChild().getHeight());
		if (this.hasRChild())
			newH = Math.max(newH, 1 + this.getRChild().getHeight());
		if (newH == height)
			return; //高度没有发生变化则直接返回 
		height = newH; //否则更新高度 
		if (this.hasParent())
			this.getParent().updateHeight(); //递归更新祖先的高度 

	}

	/******与 size 相关的方法******/
	/**
	 * 取以该结点为根的数的结点数
	 * @return
	 */
	public int getSize() {
		return size;
	}

	/**
	 * 更新当前结点及其祖先的子孙数
	 */
	public void updateSize() {
		this.size = 1; //初始化为 1,结点本身 
		if (this.hasLChild())
			size += this.getLChild().getSize();//加上左子树规模 
		if (this.hasRChild())
			size += this.getRChild().getSize();//加上右子树规模
		if (this.hasParent())
			this.getParent().updateSize();//递归更新祖先的规模 

	}

	/******与 parent 相关的方法******/
	/**
	 * 取父结点
	 * @return
	 */
	public BinTreeNode getParent() {
		return this.parent;
	}

	/**
	 * 断开与父亲的关系
	 */
	public void sever() {
		if (!this.hasParent())
			return;
		if (this.isLChild())
			this.parent.lChild = null;
		else
			this.parent.rChild = null;
		parent.updateHeight();
		parent.updateSize();
		this.parent = null;

	}

	/******与 lChild 相关的方法******/
	/**
	 * 取左孩子
	 * @return
	 */
	public BinTreeNode getLChild() {
		return this.lChild;
	}

	/**
	 * 设置当前结点的左孩子,返回原左孩子 
	 * @param lc
	 * @return
	 */
	public BinTreeNode setLChild(BinTreeNode lc) {
		BinTreeNode oldLC = this.lChild;
		if (this.hasLChild())
			this.lChild.sever();//断开当前左孩子与结点的关系 
		if (lc != null) {
			lc.sever(); //更新当前结点及其祖先规模 
			this.lChild = lc; //确定父子关系 
			lc.parent = this;
			this.updateHeight(); //更新当前结点及其祖先规模 
			this.updateSize(); //更新当前结点及其祖先规模 
		}
		return oldLC; //返回原左孩子 
	}

	/******与 rChild 相关的方法******/
	/**
	 * 
	 * @return
	 */
	public BinTreeNode getRChild() {
		return this.rChild;
	}

	/**
	 *  设置当前结点的右孩子,返回原右孩子
	 * @param rc
	 * @return
	 */
	public BinTreeNode setRChild(BinTreeNode rc) {
		BinTreeNode oldRC = this.rChild;
		if (this.hasRChild())
			this.rChild.sever(); //断开当前右孩子与结点的关系
		if (rc != null) {
			rc.sever(); //断开lc与其父结点的关系
			this.rChild = rc; //确定父子关系
			rc.parent = this;
			this.updateSize(); //更新当前结点及其祖先高度
			this.updateSize(); //更新当前结点及其祖先规模
		}
		return oldRC; //返回原右孩子

	}
}
